package com.ubb.dbms.core.fileManagers.indexFileManager.bPlusTree;

import com.ubb.dbms.core.fileManagers.indexFileManager.IndexFileIO;
import com.ubb.dbms.core.fileManagers.indexFileManager.IndexFileManager;

public class BPlusTree {
        private Node mRootNode;
        private static final int T = IndexFileManager.T;
        private boolean firstNode = true;
        private IndexFileIO indexFileIO;
        
        public BPlusTree(IndexFileIO indexFileIO) { 
        	this.indexFileIO = indexFileIO;
        	Node node = new Node(indexFileIO);
        	node.setmIsLeafNode(true);   
        	mRootNode = node;       
        }
        
        public BPlusTree(Node node, IndexFileIO indexFileIO) {
            this.mRootNode = node;   
        	this.indexFileIO = indexFileIO;
            node.setIndexFileIO(indexFileIO);
        }
       
        public void add(int key, Object object) {
                Node rootNode = mRootNode;
                if (rootNode.getmNumKeys() == (2 * T - 1)) {
                        Node newRootNode = new Node(this.indexFileIO);
                        mRootNode = newRootNode;
                        newRootNode.setmIsLeafNode(false);
                        mRootNode.setmChildNode(rootNode.getRowNr(), 0);
                        splitChildNode(newRootNode, 0, rootNode); // Split rootNode and move its median (middle) key up into newRootNode.
                        rootNode.updateNodeInFile();
                        insertIntoNonFullNode(newRootNode, key, object); // Insert the key into the B-Tree with root newRootNode.
                        newRootNode.updateNodeInFile();
                        newRootNode.updateHeaderInFileForNode();
                } else {
                        insertIntoNonFullNode(rootNode, key, object); // Insert the key into the B-Tree with root rootNode.
                        if (firstNode) {
                        	mRootNode.updateHeaderInFileForNode();
                        	firstNode = false;
                        }
                }
        }
       
        // Split the node, node, of a B-Tree into two nodes that contain T-1 (and T) elements and move node's median key up to the parentNode.
        // This method will only be called if node is full; node is the i-th child of parentNode.
        // All internal keys (elements) will have duplicates within the leaf nodes.
        void splitChildNode(Node parentNode, int i, Node node) {
                Node newNode = new Node(this.indexFileIO);
                newNode.setmIsLeafNode(node.ismIsLeafNode());
                newNode.setmNumKeys(T);
                for (int j = 0; j < T; j++) { // Copy the last T elements of node into newNode. Keep the median key as duplicate in the first key of newNode.
                        newNode.getmKeys()[j] = node.getmKeys()[j + T - 1];
                        newNode.getmObjects()[j] = node.getmObjects()[j + T - 1];
                }
                
                // TODO create the node in index file
                // FIXME 
                if (!newNode.ismIsLeafNode()) {
                        for (int j = 0; j < T + 1; j++) { // Copy the last T + 1 pointers of node into newNode.
                                newNode.setmChildNode(node.getmChildNodeOffset(j + T - 1), j);
                        }
                        for (int j = T; j <= node.getmNumKeys(); j++) {
                        		node.setmChildNode(0, j);
                        }
                        newNode.updateNodeInFile();
                } else {
                        // Manage the linked list that is used e.g. for doing fast range queries.
                        newNode.setmNextNode(node.getmNextNodeOffset());
                        newNode.updateNodeInFile();
                        node.setmNextNode(newNode.getRowNr());
                }
                for (int j = T - 1; j < node.getmNumKeys(); j++) {
                        node.getmKeys()[j] = 0;
                        node.getmObjects()[j] = null;
                }
                node.setmNumKeys(T - 1);
               
                // Insert a (child) pointer to node newNode into the parentNode, moving other keys and pointers as necessary.
                for (int j = parentNode.getmNumKeys(); j >= i + 1; j--) {
                        parentNode.setmChildNode(parentNode.getmChildNodeOffset(j), j + 1);
                }
                parentNode.setmChildNode(newNode.getRowNr(), i + 1);        
                for (int j = parentNode.getmNumKeys() - 1; j >= i; j--) {
                        parentNode.getmKeys()[j + 1] = parentNode.getmKeys()[j];
                        parentNode.getmObjects()[j + 1] = parentNode.getmObjects()[j];
                }
                parentNode.getmKeys()[i] = newNode.getmKeys()[0];
                parentNode.getmObjects()[i] = newNode.getmObjects()[0];
                parentNode.setmNumKeys(parentNode.getmNumKeys() + 1);
        }
       
        // Insert an element into a B-Tree. (The element will ultimately be inserted into a leaf node).
        void insertIntoNonFullNode(Node node, int key, Object object) {
                int i = node.getmNumKeys() - 1;
                if (node.ismIsLeafNode()) {
                        // Since node is not a full node insert the new element into its proper place within node.
                        while (i >= 0 && key < node.getmKeys()[i]) {
                                node.getmKeys()[i + 1] = node.getmKeys()[i];
                                node.getmObjects()[i + 1] = node.getmObjects()[i];
                                i--;
                        }
                        i++;
                        node.getmKeys()[i] = key;
                        node.getmObjects()[i] = object;
                        node.setmNumKeys(node.getmNumKeys() + 1);
                        node.updateNodeInFile();
                } else {
                        // Move back from the last key of node until we find the child pointer to the node
                        // that is the root node of the subtree where the new element should be placed.
                        while (i >= 0 && key < node.getmKeys()[i]) {
                                i--;
                        }
                        i++;
                        Node childNode = node.getmChildNode(i);
                        if (childNode.getmNumKeys() == (2 * T - 1)) {
                                splitChildNode(node, i, childNode);
                                if (key > node.getmKeys()[i]) {
                                        i++;
                                }
                                childNode.updateNodeInFile();
                                node.updateNodeInFile();
                        }
                        insertIntoNonFullNode(node.getmChildNode(i), key, object);
                }
        }      
       
        // Recursive search method.
        public Object search(Node node, int key) {              
                int i = 0;
                while (i < node.getmNumKeys() && key > node.getmKeys()[i]) {
                        i++;
                }
                if (i < node.getmNumKeys() && key == node.getmKeys()[i]) {
                        return node.getmObjects()[i];
                }
                if (node.ismIsLeafNode()) {
                        return null;
                } else {
                        return search(node.getmChildNode(i), key);
                }      
        }

        // Recursive search method.
        public Node searchForNode(Node node, int key) {              
                int i = 0;
                while (i < node.getmNumKeys() && key > node.getmKeys()[i]) {
                        i++;
                }
                if (i < node.getmNumKeys() && key == node.getmKeys()[i]) {
                        return node;
                }
                if (node.ismIsLeafNode()) {
                        return null;
                } else {
                        return searchForNode(node.getmChildNode(i), key);
                }      
        }
       
        public Node searchForNode(int key) {
            return searchForNode(mRootNode, key);
        }

        public Object search(int key) {
                return search(mRootNode, key);
        }
       
        // Iterative search method.
        public Object search2(Node node, int key) {
                while (node != null) {
                        int i = 0;
                        while (i < node.getmNumKeys() && key > node.getmKeys()[i]) {
                                i++;
                        }
                        if (i < node.getmNumKeys() && key == node.getmKeys()[i]) {
                                return node.getmObjects()[i];
                        }
                        if (node.ismIsLeafNode()) {
                                return null;
                        } else {
                                node = node.getmChildNode(i);
                        }
                }
                return null;
        }
       
        public Object search2(int key) {
                return search2(mRootNode, key);
        }
       
        // Inorder walk over the tree.
        public String toString() {
                String string = "";
                Node node = mRootNode;          
                while (!node.ismIsLeafNode()) {                    
                        node = node.getmChildNode(0);
                }              
                while (node != null) {
                        for (int i = 0; i < node.getmNumKeys(); i++) {
                                string += node.getmObjects()[i] + ", ";
                        }
                        node = node.getmNextNode();
                }
                return string;
        }
       
        // Inorder walk over parts of the tree.
        public String toString(int fromKey, int toKey) {
                String string = "";
                Node node = getLeafNodeForKey(fromKey);
                while (node != null) {
                        for (int j = 0; j < node.getmNumKeys(); j++) {
                                string += node.getmObjects()[j] + ", ";
                                if (node.getmKeys()[j] == toKey) {
                                        return string;
                                }
                        }
                        node = node.getmNextNode();
                }
                return string;
        }
       
        public Node getLeafNodeForKey(int key) {
                Node node = mRootNode;
                while (node != null) {
                        int i = 0;
                        while (i < node.getmNumKeys() && key > node.getmKeys()[i]) {
                                i++;
                        }
                        if (i < node.getmNumKeys() && key == node.getmKeys()[i]) {
                        	if (node.ismIsLeafNode()) {
                        		return node;
                        	}
                            node = node.getmChildNode(i + 1);
                            while (!node.ismIsLeafNode()) {                    
                                    node = node.getmChildNode(0);
                            }
                            return node;
                        }
                        if (node.ismIsLeafNode()) {
                                return null;
                        } else {
                                node = node.getmChildNode(i);
                        }
                }
                return null;
        }
       
//        public static void main(String[] args) {
//                BPlusTree bPlusTree = new BPlusTree();
//                
//                bPlusTree.add(2, new String("2"));
//                bPlusTree.add(6, new String("6"));
//                bPlusTree.add(10, new String("10"));
//                bPlusTree.add(50, new String("50"));
//                
//                int primeNumbers[] = new int[] { 2, 3, 5, 7, 11, 13, 19, 23, 37, 41, 43, 47, 53, 59, 67, 71, 61, 73, 79, 89,
//                                97, 101, 103, 109, 29, 31, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 17, 83, 107 };
//               
//                for (int i = 0; i < primeNumbers.length; i++) {
//                        bPlusTree.add(primeNumbers[i], String.valueOf(primeNumbers[i]));
//                }              
//               
//                for (int i = 0; i < primeNumbers.length; i++) {
//                        String value = String.valueOf(primeNumbers[i]);
//                        Object searchResult = (Object) bPlusTree.search(primeNumbers[i]);                      
//                        if (!value.equals(searchResult)) {
//                                System.out.println("Oops: Key " + primeNumbers[i] + " retrieved object " + searchResult);
//                        }
//                }              
//               
//                System.out.println(bPlusTree.search(11));
//                System.out.println(bPlusTree.search(17));
//                System.out.println(bPlusTree.toString());
//                System.out.println(bPlusTree.toString(19, 71));
//        }
}
